package com.tgy.algorithm.base;

import java.util.Arrays;

public class _快速排序_01 {

    public static int[] dutchFlag(int[] nums,int left,int right) {
        if (left >= right) {
            return null;
        }

        int[] res = new int[2];

        int pivot = nums[right];
        int preIndex = left - 1;
        int index = left;
        int postIndex = right - 1;
        while (index <= postIndex) {

            if(nums[index] < pivot) {
//                if(preIndex + 1 != index) {
//                    nums[preIndex + 1] = nums[index];
                swap(nums,preIndex+1,index);
                preIndex++;
//                }
                index++;
            }else  if(nums[index] == pivot) {
                index++;
            }else {
                swap(nums,postIndex,index);
                postIndex--;
            }
        }
        // index == postIndex
        swap(nums,postIndex+1,right);
        res[0] = preIndex;
        res[1] = index + 1;
        return res;
    }

    public static void quickSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        doQuickSort(nums, 0, nums.length - 1);
    }

    public static void doQuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int[] res = dutchFlag(nums, left, right);
        if(res != null) {
            doQuickSort(nums, left, res[0]);
            doQuickSort(nums, res[1],right);
        }
    }

    public static void swap(int[] nums,int left,int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static int[] generateRandomArray(int len, int min, int max) {
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = (int) (Math.random() * (max - min + 1)) + min;
        }
        return res;
    }

    public static void main(String[] args) {

//        int[] nums = {3,2,1,5,6,2};
        int[] nums = generateRandomArray(20, 1, 10);
        System.out.println(Arrays.toString(nums));
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
//        int[] res = dutchFlag(nums,0,nums.length-1);

//        System.out.println(Arrays.toString(nums));
//        System.out.println(Arrays.toString(res));
    }
}
